// 假设 n 个节点存在二叉排序树的个数是 G(n)，令 f(i) 为以 i 为根节点
// 的二叉搜索树的个数
// 当 i 为根节点时，其左子树节点个数为 i-1 个，右子树节点个数为 n - i 个
// 根据 BST 的定义，如果整数 1 到 n 中的整数 k 作为根节点值，则 1 ~ k - 1 会去构建左子树
// k + 1 ~ n 会构建右子树

var numTrees = function (n) {
  const dp = new Array(n + 1).fill(0);
  dp[0] = 1;
  dp[1] = 1;
  for (let i = 2; i <= n; i++) {
    for (let j = 0; j <= i - 1; j++) {
      dp[i] += dp[j] * dp[i - j - 1];
    }
  }
  return dp[n];
}